package LeetCode.exercise;

import java.util.*;

public class LC433 {

    char[] chars = {'A', 'C', 'G', 'T'};

    public static void main(String[] args) {
        LC433 main = new LC433();
        args = new String[]{"AACCGGTA", "AACCGCTA", "AAACGGTA"};
        System.out.println(main.minMutation("AACCGGTT", "AACCGCTA", args));
    }

    public int minMutation1(String startGene, String endGene, String[] bank) {
        Map<String, Boolean> hashMap = new HashMap<>();
        Map<String, Boolean> flag = new HashMap<>();
        for (String tmp : bank) {
            hashMap.put(tmp, true);
        }
        Queue<String> q = new LinkedList<>();
        q.offer(startGene);
        flag.put(startGene, true);
        int ret = 0;
        while (!q.isEmpty()) {
            int res = 0;
            String tmp = q.poll();
            for (int i = 0; i < tmp.length(); i++) {
                for (int j = 0; j < 4; j++) {
                    StringBuffer sb = new StringBuffer(tmp);
                    sb.setCharAt(i, chars[j]);
                    if (hashMap.containsKey(sb.toString()) && !flag.containsKey(sb.toString())) {
                        q.offer(sb.toString());
                        flag.put(sb.toString(), true);
                        res = 1;
                        if (endGene.contentEquals(sb)) {
                            return ret + res;
                        }
                    }
                }
            }
            ret += res;
        }
        return -1;
    }
    public int minMutation2(String startGene, String endGene, String[] bank) {
        Set<String> set = new HashSet<>();
        Set<String> flag = new HashSet<>();
        Collections.addAll(set, bank);
        if(startGene.equals(endGene)){
            return 0;
        }
        if(!set.contains(endGene)){
            return -1;
        }
        int res = 0;
        Queue<String> q = new LinkedList<>();
        q.offer(startGene);
        flag.add(startGene);
        while(!q.isEmpty()){
            int num = 0;
            String tmp = q.poll();
            for(int i = 0; i < tmp.length(); i++){
                for(char ch : chars){
                    StringBuilder sb = new StringBuilder(tmp);
                    sb.setCharAt(i, ch);
                    String str = sb.toString();
                    if(set.contains(str) && !flag.contains(str)){
                        q.offer(str);
                        num = 1;
                        flag.add(str);
                        if(str.equals(endGene)){
                            return res + num;
                        }
                    }
                }
            }
            res += num;
        }
        return -1;
    }
    public int minMutation(String startGene, String endGene, String[] bank) {
        if(startGene.equals(endGene)){
            return 0;
        }
        char[] chars = {'A', 'C', 'G', 'T'};
        Set<String> set = new HashSet<>();
        Set<String> flag = new HashSet<>();
        for(String tmp : bank){
            set.add(tmp);
        }
        if(!set.contains(endGene)){
            return -1;
        }
        Queue<String> q = new LinkedList<>();
        q.offer(startGene);
        flag.add(startGene);
        int res = 0;
        while(!q.isEmpty()){
            int size = q.size();
            res++;
            String tmp = q.poll();
            while(size-- > 0){
                for(int i = 0; i < 8; i++){
                    char[] c = tmp.toCharArray();
                    for(int j = 0; j < 4; j++){
                        c[i] = chars[j];
                        String next = new String(c);
                        if(next.equals(endGene)){
                            return res;
                        }
                        if(set.contains(next) && !flag.contains(next)){
                            q.offer(next);
                            flag.add(next);
                        }
                    }
                }
            }
        }
        return -1;
    }
}
